Corelab Seminar
2008-2009
Thanasis Lianeas (NTUA)
Undirected graph connectivity is in L
Abstract. One of the most important and recent results in computational complexity is the fact that the classes L and SL coincide. This was proven by Reingold in 2005 by presenting an algorithm that solves the undirected s-t connectivity problem in logarithmic space. The algorithm relies on results from graph theroy and linear algebra. We will see basic facts of the class SL, results concerning expander graphs and their behavior on some graph operations, the basic steps of the algorithm and the way they lead us to the desired conclusion.